/**
 * Created by Administrator on 2017/2/14.
 */
public class Test3 {
    public static void main(String[] args) {
        char[] str = "a".toCharArray();
        char[] pattern = ".*".toCharArray();
        System.out.println(match(str, pattern));
    }

    public static boolean match(char[] str, char[] pattern) {
        return match(str, 0, pattern, 0);
    }

    private static boolean match(char[] str, int strIndex, char[] pattern, int patIndex) {
        if (str.length == strIndex && patIndex == pattern.length) {
            return true;
        }
        //pattern先到尾，匹配失败
        if (strIndex != str.length && patIndex == pattern.length) {
            return false;
        }

        //模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
        if (patIndex + 1 < pattern.length && pattern[patIndex + 1] == '*') {
            if ((strIndex != str.length) && (pattern[patIndex] == str[strIndex] || pattern[patIndex] == '.')) {
                //aaa a*aaa
                return match(str, strIndex, pattern, patIndex + 2)//模式后移两位
                        //a*b aab
                        || match(str, strIndex + 1, pattern, patIndex + 1)//字符串后移一位，模式后移一位
                        //aaaaab a*b
                        || match(str, strIndex + 1, pattern, patIndex); //字符串后移一位，模式不变
            } else {
                //aa ab*a
                return match(str, strIndex, pattern, patIndex + 2);//模式后移两位
            }
        }
        //abc abc 或 a.c
        if ((strIndex != str.length) && (pattern[patIndex] == '.' || pattern[patIndex] == str[strIndex])) {
            return match(str, strIndex + 1, pattern, patIndex + 1);
        }
        return false;
    }
}
